Entropy encoding is a data compression scheme that assigns codes to symbols so as to match code lengths with the probabilities of the symbols. Typically, entropy encoders are used to compress data by replacing symbols represented by equal-length codes with symbols represented by codes where the length of each codeword is proportional to the negative logarithm of the probability. Therefore, the most common symbols use the shortest codes.
Two of the most common entropy encoding techniques are Huffman coding and arithmetic coding. If the approximate entropy characteristics of a data stream are known in advance, a simpler static code may be useful. These static codes include universal codes (e.g., Elias gamma coding, Fibonacci coding) and Golomb codes (e.g., unary coding, Rice coding).
Golomb coding uses a tunable parameter M to divide an input value N (e.g., a number to be encoded) into a quotient q and a remainder r. The quotient q can be sent to a decoder in unary coding, followed by the remainder r in truncated binary encoding or other variable-length binary encodings (e.g., arithmetic, Huffman encodings).
Rice coding is a special case of Golomb coding and is equivalent to Golomb coding where the tunable parameter M is a power of two. Thus Rice coding can be efficiently implemented on digital devices, since the division operation becomes a bitshift operation and the remainder operation becomes a bitmask operation. Rice coding is used as the entropy encoding stage in a number of lossless image compression and audio data compression methods.
Several techniques exist for selecting a tunable parameter M (i.e., the divisor) that works best for the data to be encoded. For example, one technique adjusts the value of the tunable parameter dynamically during encoding based on the data size. Such a technique, however, may not be optimal for the particular application for which the technique is being used. One example of such an application would be screen sharing in a video conferencing application where the shared screen is to be compressed and sent to a recipient. Such an application often has low bandwidth and fast screen changes which requires the compression coding of the shared screen to be fast and efficient.